Everything about Space-filling Curve totally explained
Space-filling curves or
Peano curves are
curves, first described by
Giuseppe Peano (1858–1932), whose ranges contain the entire 2-dimensional
unit square (or the 3-dimensional unit cube).
Intuitively, a "continuous curve" in the 2-dimensional plane or in the 3-dimensional space can be thought of as the "path of a continuously moving point". To eliminate the inherent vagueness of this notion,
Jordan in 1887 introduced the following rigorous definition, which has since been adopted as the precise description of the notion of a "continuous curve":
» A
curve (with endpoints) is a
continuous function whose domain is the
unit interval [0,1].
In the most general form, the range of such a function may lie in an arbitrary topological space, but in the most common cases, the range will lie in a
Euclidean space such as the 2-dimensional plane (a "plane curve") or the 3-dimensional space ("space curve").
Sometimes, the curve is identified with the range or image of the function (the set of all possible values of the function), instead of the function itself. It is also possible to define curves without endpoints to be a continuous function on the real line (or on the open unit interval (0,1)).
In
1890,
Peano discovered a densely self-intersecting curve which passed through every point of the unit square. This was the first example of a space-filling curve. Peano's purpose was to construct a continuous mapping from the
unit interval onto the
unit square, motivated by
Georg Cantor's earlier counterintuitive result that the infinite number of points in a
unit interval is the same
cardinality as the infinite number of points in any finite-dimensional
manifold, such as the
unit square.
It was common to associate the vague notions of "thinness" and "1-dimensionality" to curves; all normally encountered
curves were
piecewise smooth (that is, have piecewise continuous derivatives), and such curves can't fill up the entire unit square. Therefore, Peano's space filling curve was found to be highly counterintuitive.
From Peano's example, it was easy to deduce continuous curves whose ranges contained the n-dimensional
hypercube (for any
positive integer n). It was also easy to extend Peano's example to continuous curves without endpoints which filled the entire n-dimensional Euclidean space (where n is 2, 3, or any other positive integer).
Most well-known space-filling curves are constructed iteratively as the limit of a sequence of
piecewise linear continuous curves.
Outline of the construction of a space-filling curve
Let
. The composition
of
and
is a continuous function mapping the
Cantor set onto the entire unit square. (Alternatively, we could use the theorem that every
compact metric space is a continuous image of the
Cantor set to get the function
.)
Finally, one can extend
to a continuous function
whose domain is the entire unit interval
. This can be done either by using the
Tietze extension theorem on each of the components of
, or by simply extending
"linearly" (that is, on each of the deleted open interval
in the construction of the
Cantor set, we define the extension part of
on
to be the line segment within the unit square joining the values
and
).
Properties
Approximation curves remain within a bounded portion of n-dimensional space, but their lengths increase without bound.
The space-filling curve is always self-intersecting, although the approximation curves in the sequence can be self-avoiding. There can't be any non-self-intersecting (for example
injective) continuous curve filling up the unit square, because that will make the curve a
homeomorphism from the unit interval onto the unit square (any continuous
bijection from a
compact space onto a
Hausdorff space is a homeomorphism), but the unit-square (which has no cut-point) isn't homeomorphic to the unit interval (all points of which, except the endpoints, are cut-points).
Proof that a square and its side contain the same number of points
The highly counterintuitive result that the
cardinality of a
unit interval is the same as the cardinality of any finite-dimensional
manifold, such as the
unit square, was first obtained by Cantor in 1878, but it can be more intuitively proved using space-filling curves.
Space-filling curves are always self-intersecting. This means that they're not
injective, and as a consequence not
bijective. Since a bijection between a set A and a set B is needed to prove that A and B have the same cardinality, space-filling curves are not a direct proof that a square (or cube or hypercube) has as many points as its side, but they can be used to obtain such a proof.
Intuitively, consider that the difficulty resided in showing that a function of the unit interval can fill a square or a cube or a hypercube, and this task was successfully accomplished by Peano. Indeed, being self-intersecting, his curves even manage to "overfill" the square. In other words, although Peano curves are not injective (because they overfill the space), they're
surjective (because they fill it).
More formally, consider a space-filling curve which maps a unit interval [0,1] onto a unit square [0,1]×[0,1]. One can define a
right inverse for it which will be an injection from [0,1]×[0,1] into [0,1]. And
x goes to <
x,0> is an injection from [0,1] into [0,1]×[0,1]. Using the
Cantor–Bernstein–Schroeder theorem, we get a bijection between [0,1] and [0,1]×[0,1]. We conclude that [0,1] and [0,1]×[0,1] have the same cardinality.
One advantage of this proof is that, since an explicit definition of the right inverse is easily given, it doesn't require the use of the
axiom of choice. For example, in the Hilbert curve each point in the square is the
image of from one to four points in the line segment. When one of the coordinates is a rational number with a power of two in the denominator, that coordinate can be approached either from below or above giving two (not necessarily distinct) values for the
preimage. Similarly, when both are such, then there are four (not necessarily distinct). Since the number of possible preimages for each point is finite (indeed less than or equal to four), one can just choose the smallest of them systematically, making the axiom of choice unnecessary.
Similarly, finite-dimensional space-filling curves can be used to prove, in general, that any finite-dimensional space contains the same number of points as any
line or
line segment.
The Hahn-Mazurkiewicz theorem
The Hahn-Mazurkiewicz theorem is the following characterization of general continuous curves:
» A Hausdorff topological space is a continuous image of the unit interval if and only if it's a compact, connected, locally connected second-countable space.
Note: In many formulations of the Hahn-Mazurkiewicz theorem, "second-countable" is replaced by "metrizable". These two formulations are equivalent. In one direction a compact Hausdorff space is a
normal space and, by the
Urysohn metrization theorem, second-countable then implies metrizable. Conversely a compact metric space is second-countable.
Literature
- Hans Sagan, Space-Filling Curves, Springer-Verlag 1994. ISBN 0387942653.
- B. B. Mandelbrot, The Fractal Geometry of Nature, Ch. 7, "Harnessing the Peano Monster Curves", W. H. Freeman, 1982
- Douglas M. McKenna, "SquaRecurves, E-Tours, Eddies, and Frenzies: Basic Families of Peano Curves on the Square Grid", a chapter from The Lighter Side of Mathematics - Proceedings of the Eugene Strens Memorial Conference on Recreational Mathematics and its History, Math. Assoc. of America, 1994
- G. Peano, Sur une courbe, qui remplit toute une aire plane. Math. Ann 36 (1890), 157-160.
Further Information
Get more info on 'Space-filling Curve'.
|
External Link Exchanges
Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:
<a href="http://space-filling_curve.totallyexplained.com">Space-filling curve Totally Explained</a>
Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned. |
